package lru

import "container/list"

// Cache 是LRU缓存。并发访问不安全。
type Cache struct {
	maxBytes int64 //maxBytes 是允许使用的最大内存
	nbytes   int64 //nbytes 是当前已使用的内存
	ll       *list.List
	cache    map[string]*list.Element
	// 可选，并在清除条目时执行。
	OnEvicted func(key string, value Value) //OnEvicted 是某条记录被移除时的回调函数，可以为 nil。
}

type entry struct {
	key   string
	value Value
}

// Value 使用Len计算它需要多少字节
type Value interface {
	Len() int
}

// New 方便实例化 Cache，实现 New() 函数：
func New(maxBytes int64, onEvicted func(string, Value)) *Cache {
	return &Cache{
		maxBytes:  maxBytes,
		ll:        list.New(),
		cache:     make(map[string]*list.Element),
		OnEvicted: onEvicted,
	}
}

// Add 将值添加到缓存中。
func (c *Cache) Add(key string, value Value) {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		kv := ele.Value.(*entry)
		c.nbytes += int64(value.Len() - kv.value.Len())
		kv.value = value // 替换原有的Key
	} else {
		ele := c.ll.PushFront(&entry{key, value}) // 不需要替换原有的Key
		c.cache[key] = ele
		c.nbytes += int64(len(key) + value.Len())
	}
	// 超过最大允许内存，移除最旧的元素
	for c.maxBytes != 0 && c.maxBytes < c.nbytes {
		c.RemoveOldest()
	}
}

// Get 查找键的值
func (c *Cache) Get(key string) (value Value, ok bool) {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		kv := ele.Value.(*entry)
		return kv.value, true
	}
	return
}

// RemoveOldest 删除最旧的项目
func (c *Cache) RemoveOldest() {
	ele := c.ll.Back() //如果列表为空，则返回nil ；否则列表l的最后一个元素。
	if ele != nil {
		c.ll.Remove(ele)
		kv := ele.Value.(*entry)
		delete(c.cache, kv.key)                                // 这是Map删除一个元素的API ！！！
		c.nbytes -= int64(len(kv.key)) + int64(kv.value.Len()) // 删除一个map所占的空间
		if c.OnEvicted != nil {
			c.OnEvicted(kv.key, kv.value)
		}
	}
}

// Len 缓存条目数
func (c *Cache) Len() int {
	return c.ll.Len()
}
